import java.util.HashMap;
import java.util.Map;

class Solution {

    /** 最小覆盖子串 76题
     *
     * @param ss 原定字符串 在其中找最小覆盖子串
     * @param tt 目标找的子串
     * @return
     */

    public String minWindow(String ss, String tt) {

        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        int[] hash1 = new int[128];
        int kinds = 0;
        for(char ch : t)
            if(hash1[ch]++ == 0) kinds++;

        int[] hash2 = new int[128];
        int start = -1;
        int min = Integer.MAX_VALUE;
        for (int right = 0, left = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            if(++hash2[in] == hash1[in]){ //进窗口 + 更新count
                count++;
            }
            while (count == kinds){ // 判断 + 更新count
                if(right - left + 1 < min){
                    start = left;
                    min = right - left + 1;
                }
                char out = s[left++];
                if(hash2[out]-- == hash1[out]){
                    count--;
                }
            }
        }
        if(start == -1) return new String();

        return ss.substring(start,start + min);
    }


    public String minWindow1(String s, String t) {
        Map<Character,Integer> map1 = new HashMap<>();
        for(char ch : t.toCharArray()){
            map1.put(ch, map1.getOrDefault(ch,0) + 1);
        }
        int start = -1;
        int min = Integer.MAX_VALUE;
        Map<Character,Integer> map2 = new HashMap<>();

        for (int rigth = 0, left = 0, count = 0 ; rigth < s.length(); rigth++) {

            char in = s.charAt(rigth);
            if(map1.containsKey(in)){
                map2.put(in,map2.getOrDefault(in,0)+1);
                if(map2.get(in) == map1.get(in)){
                    count++;
                }
            }

            while (count == map1.size()){
                if(min > rigth - left + 1){
                    start = left;
                    min = rigth - left + 1;
                }

                char out = s.charAt(left++);
                if(map1.containsKey(out)){
                    if(map2.get(out) == map1.get(out)) {
                        count--;
                    }
                    map2.put(out,map2.get(out) - 1);
                }
            }
        }
        if (start == -1) return new String();

        return s.substring(start,start + min);
    }

    public static void main(String[] args) {

    }
}